Kruskals Minimum Spanning Tree Algorithm
Kruskal's Minimum Spanning Tree (MST) Algorithm is a popular graph algorithm that is used to find the minimum spanning tree of an undirected, connected, and weighted graph. The algorithm works by constructing a tree from the graph's edges in increasing order of their weights, while ensuring that adding a new edge does not form a cycle in the tree. The main objective of Kruskal's algorithm is to connect all vertices in the graph, such that the total weight of the edges in the resulting tree is minimized. This is particularly useful in various applications like network design, clustering, and transportation planning, where the goal is to create an efficient and cost-effective connection between multiple nodes.
The algorithm starts by sorting all the edges of the graph in non-decreasing order of their weights. Then, it initializes an empty tree, and iteratively adds edges to the tree while ensuring that it remains acyclic. To check for cycles, Kruskal's algorithm typically employs a disjoint-set data structure, which allows for efficient union and find operations. The process continues until the tree contains all the vertices of the graph, or all edges have been considered. At the end of the algorithm, the resulting tree is a minimum spanning tree of the input graph, connecting all vertices with the minimum possible total weight. Kruskal's algorithm has a time complexity of O(E log E), where E is the number of edges in the graph, making it an efficient solution for finding the minimum spanning tree in large graphs.
#include <iostream>
using namespace std;
#define V 6
#define INFINITY 99999
int graph[V][V] = {
{0, 4, 1, 4, INFINITY, INFINITY},
{4, 0, 3, 8, 3, INFINITY},
{1, 3, 0, INFINITY, 1, INFINITY},
{4, 8, INFINITY, 0, 5, 7},
{INFINITY, 3, 1, 5, 0, INFINITY},
{INFINITY, INFINITY, INFINITY, 7, INFINITY, 0}};
void findMinimumEdge()
{
for (int i = 0; i < V; i++)
{
int min = INFINITY;
int minIndex = 0;
for (int j = 0; j < V; j++)
{
if (graph[i][j] != 0 && graph[i][j] < min)
{
min = graph[i][j];
minIndex = j;
}
}
cout << i << " - " << minIndex << "\t" << graph[i][minIndex] << "\n";
}
}
int main()
{
findMinimumEdge();
return 0;
}
